// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2002 University of Colorado
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: bitvector.h,v 1.12 2010-03-11 15:16:38 carzanig Exp $
//
#ifndef SIENA_BITVECTOR_H
#define SIENA_BITVECTOR_H

#include <cstddef> /* for size_t */
#include <climits> /* for CHAR_BIT*/
#include "siena/allocator.h"

namespace siena {

class bitvector;
class ibitvector;

typedef unsigned long		bv_atom_t;
//
// hopefully this stuff is statically optimized by the compiler
//
static const unsigned char	bv_atom_bits = sizeof(bv_atom_t) * CHAR_BIT;
static const unsigned char	bv_atom_shift = (bv_atom_bits == 32) ? 5 : ((bv_atom_bits == 64) ? 6 : 4);
static const unsigned char	bv_atom_mask = bv_atom_bits - 1;

/** fixed-size bit vector.
 *
 *  This bitvector is implemented by a single array.
 **/
class bitvector {
public:
    /** constructs a bitvector capable of holding <em>size</em> bits
     **/
				bitvector(size_t size, bool v = false) throw();
				bitvector(const bitvector & bv) throw();
				~bitvector() throw();
    
    bool			test(size_t pos) const throw();
    bool			operator[](size_t pos) const throw();
    bool			set(size_t pos) throw();
    bool			clear(size_t pos) throw();

    void			set(const ibitvector & x) throw();

    void			clear() throw();
    /** number of bits set to 1 **/
    size_t			get_count() const throw();
    /** total bit capacity **/
    size_t			get_size() const throw();

    bool			operator < (const bitvector & x) const throw();
    bool			operator ==(const bitvector & x) const throw();
    bitvector &			operator = (const bitvector & x) throw();
    bitvector &			operator &= (const bitvector & x) throw();

protected:
    bv_atom_t *			elements; 
    const size_t		size;		// number of bits
    size_t			count;		// number of bits set to 1

    static size_t		set(bv_atom_t * x, 
				    bv_atom_t * xe, 
				    const bv_atom_t * y, 
				    const bv_atom_t *ye) throw();

    static size_t atom_size(size_t s) { 
	return (s) ? ((--s >> bv_atom_shift) + 1) : 0;
    }

    size_t element_size() { 
	return atom_size(size);
    }

    static size_t atom_position(size_t s) { 
	return s >> bv_atom_shift;
    }

    static size_t bit_position(size_t s) { 
	return (s & bv_atom_mask);
    }

    bitvector(bv_atom_t *, size_t size, bool v = false) throw();
    bitvector(bv_atom_t *, const bitvector & bv) throw();
};

/** utility wrapper for bitvector.  The only difference w.r.t. bitvector
 *  is that FABitvector is constructed with an external allocator.  We
 *  use it in XDDNodeMap.
 **/
class FABitvector: public bitvector {
public:
    FABitvector(FTAllocator & mem, const bitvector & bv) throw()
	: bitvector(new (mem) bv_atom_t[atom_size(bv.get_size())], bv) {}
    FABitvector(FTAllocator & mem, size_t size, bool v = false) throw()
	: bitvector(new (mem) bv_atom_t[atom_size(size)], size, v) {}
    ~FABitvector() throw() {}
};

/** variable-size bit vector.
 *
 *  This bit vector is implemented by a multi-index structure.
 **/
class ibitvector {
public:
				ibitvector() throw();
    
    bool			test(size_t pos) const throw();
    bool			set(size_t pos, FTAllocator &) throw();

    void			clear() throw();
    size_t			get_count() const throw();
    size_t			get_size() const throw();

private:
    struct index;
    struct block;

    static const unsigned int	block_size = 16;
    static const unsigned int	index_size = 16;

    union index_or_block {
	block *		b;
	index *		i;
    };

    struct block {
	index *		up;
	bv_atom_t	elements[block_size];
	
	block(index *) throw();
    };

    struct index {
	index *		up;
	index_or_block	down[index_size];

	index(index *) throw();
    };

    class iterator {
    public:
			iterator(const block &) throw();

	size_t		element_address() const throw();
	const block *	next_block() throw();

    private:
	index *		bi;
	size_t		addr;
	unsigned char	level;
    };

    size_t count;
    size_t size;
    block  first_block;

    friend class bitvector;
};

} // end namespace siena

#include "bitvector.icc"

#endif
